package stack;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class LRUCache {

    private Node head;

    private Node tail;

    //双向链表
    class Node{
        private int key;
        private Node next;
        private Node prev;
        private int val;

        private Node(int key, int val){
            this.key = key;
            this.val = val;
        }

        private Node(){}

    }

    HashMap<Integer,Node> map;

    int capacity;

    public LRUCache(int capacity) {
        map = new HashMap<>(capacity);
        this.capacity = capacity;
        this.head = new Node();
        this.tail = new Node();
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if(map.get(key) == null){
            return -1;
        }
        addToHead(map.get(key));
        return map.get(key).val;
    }
    
    public void put(int key, int value) {
        if(map.size() == capacity){
            int i = removeTail();
            map.remove(i);
        }
        Node node = new Node(key, value);
        addToHead(node);
        map.put(key,node);
    }

    public void addToHead(Node node){
        Node next = head.next;
        head.next = node;
        node.prev = head;
        node.next = next;
        next.prev = node;
    }
    public void moveToHead(Node node){
        addToHead(node);
        removeNode(node);
    }

    public void removeNode(Node node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public int removeTail(){
        Node prev = tail.prev;
        Node prePrev = prev.prev;
        prePrev.next = tail;
        tail.prev = prev.next;
        return prev.key;
    }

    public static void main(String[] args) {
        // 测试用例1: 基本的put和get操作
        System.out.println("=== 测试用例1: 基本的put和get操作 ===");
        LRUCache cache1 = new LRUCache(2);

        cache1.put(1, 1);
        cache1.put(2, 2);
        System.out.println("get(1): " + cache1.get(1)); // 返回 1

        cache1.put(3, 3); // 该操作会使得关键字 2 作废
        System.out.println("get(2): " + cache1.get(2)); // 返回 -1 (未找到)

        cache1.put(4, 4); // 该操作会使得关键字 1 作废
        System.out.println("get(1): " + cache1.get(1)); // 返回 -1 (未找到)
        System.out.println("get(3): " + cache1.get(3)); // 返回 3
        System.out.println("get(4): " + cache1.get(4)); // 返回 4

        // 测试用例2: 容量为1的LRU Cache
        System.out.println("\n=== 测试用例2: 容量为1的LRU Cache ===");
        LRUCache cache2 = new LRUCache(1);

        cache2.put(2, 1);
        System.out.println("get(2): " + cache2.get(2)); // 返回 1

        cache2.put(3, 2); // 关键字2被淘汰
        System.out.println("get(2): " + cache2.get(2)); // 返回 -1
        System.out.println("get(3): " + cache2.get(3)); // 返回 2

        // 测试用例3: 重复put操作
        System.out.println("\n=== 测试用例3: 重复put操作 ===");
        LRUCache cache3 = new LRUCache(2);

        cache3.put(2, 1);
        cache3.put(1, 1);
        cache3.put(2, 3); // 更新关键字2的值
        cache3.put(4, 1); // 淘汰关键字1
        System.out.println("get(1): " + cache3.get(1)); // 返回 -1
        System.out.println("get(2): " + cache3.get(2)); // 返回 3

        // 测试用例4: 访问后更新位置
        System.out.println("\n=== 测试用例4: 访问后更新位置 ===");
        LRUCache cache4 = new LRUCache(3);

        cache4.put(1, 1);
        cache4.put(2, 2);
        cache4.put(3, 3);
        System.out.println("get(1): " + cache4.get(1)); // 访问关键字1，使其变为最近使用

        cache4.put(4, 4); // 关键字2应该被淘汰(因为1被访问过，3是最近插入的，2是最久未使用的)
        System.out.println("get(2): " + cache4.get(2)); // 返回 -1
        System.out.println("get(1): " + cache4.get(1)); // 返回 1
        System.out.println("get(3): " + cache4.get(3)); // 返回 3
        System.out.println("get(4): " + cache4.get(4)); // 返回 4

        // 测试用例5: 边界情况
        System.out.println("\n=== 测试用例5: 边界情况 ===");
        LRUCache cache5 = new LRUCache(0);
        cache5.put(1, 1);
        System.out.println("get(1) with capacity 0: " + cache5.get(1)); // 可能返回异常或-1

        LRUCache cache6 = new LRUCache(1);
        System.out.println("get(1) on empty cache: " + cache6.get(1)); // 返回 -1
    }
}